package 树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <p>
 * https://leetcode-cn.com/problems/invert-binary-tree/
 * </p>
 *
 * @author AJun
 * @since 2020/8/15
 */
public class _226_翻转二叉树 {

    // 前序遍历
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;

        // 每次遍历交换左右节点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    // 后序遍历
    public TreeNode invertTree2(TreeNode root) {
        if (root == null)
            return null;

        invertTree2(root.left);
        invertTree2(root.right);

        // 每次遍历交换左右节点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        return root;
    }

    // 中序遍历
    public TreeNode invertTree3(TreeNode root) {
        if (root == null)
            return null;

        invertTree3(root.left);

        // 每次遍历交换左右节点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree3(root.left); // 这里交换过了，这里的left就是之前的right
        return root;
    }

    // 层序遍历
    public TreeNode invertTree4(TreeNode root) {
        if (root == null)
            return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode head = queue.remove();
            // 每次遍历交换左右节点
            TreeNode tmp = head.left;
            head.left = head.right;
            head.right = tmp;

            if (head.left != null)
                queue.add(head.left);
            if (head.right != null)
                queue.add(head.right);
        }
        return root;
    }

}
